package 学习计划.数据结构;

public class _59_螺旋矩阵II {
    /**
     * 纯模拟，利用一个方向数组  按照右下左上的顺序进行移动
     * 执行用时；0ms，内存消耗：39.2MB
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        int maxNum = n * n;
        int curNum = 1;
        int column = 0, row = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        while (curNum <= maxNum) {
            ret[row][column] = curNum;
            curNum++;
            int newRow = row + directions[directionIndex][0], newColumn = column + directions[directionIndex][1];
            if (newRow < 0 || newRow >= n || newColumn < 0 || newColumn >= n || ret[newRow][newColumn] != 0) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row = row + directions[directionIndex][0];
            column = column + directions[directionIndex][1];
        }
        return ret;
    }

    /**
     * 一层一层模拟
     * 执行时间：0ms，内存消耗；39.3MB
     * @param n
     * @return
     */
    public int[][] generateMatrix2(int n) {
        int num = 1;
        int[][] matrix = new int[n][n];
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        while (left <= right && top <= bottom) {
            // 向右走
            for (int column = left; column <= right; column++) {
                matrix[top][column] = num++;
            }
            // 向下走
            for (int row = top + 1; row <= bottom; row++) {
                matrix[row][right] = num++;
            }
            // 判断是否走完
            if (left < right && top < bottom) {
                // 向左走
                for (int column = right - 1; column >= left; column--) {
                    matrix[bottom][column] = num++;
                }
                // 向上走
                for (int row = bottom - 1; row > top; row--) {
                    matrix[row][left] = num++;
                }
            }

            left++;
            right--;
            top++;
            bottom--;
        }
        return matrix;
    }
}
